package DataStructPackage;

/**
 * @Auther: MFM
 * @Date: 2022/3/29 - 03 - 29 - 11:50
 * @version: 1.0
 */

public class BinarySearchTree<E extends Comparable<E>> {
    private class Node {
        public E e;
        public Node left;
        public Node right;

        public Node(E e){
            this.e = e;
            this.left=null;
            this.right=null;
        }

        @Override
        public String toString() {
            return "e=" + e;
        }
    }

    private Node root;
    private int size;

    public BinarySearchTree() {
        root = null;
        size = 0;
    }

    public Node getNode() {
        return root;
    }

    public void setNode(Node node) {
        this.root = node;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public void add(E e){
        //添加完e节点后 将root重置为树的根节点
        root = add(root,e);
    }

    /*
    * 增加功能
    * node 根节点
    *  e 元素
    * */
    private Node add(Node node,E e){
        //当node为null时表示已经是数的叶子节点 在这里创建新的叶子节点
        if(node == null){
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0){
            node.left = add(node.left,e);
        }else if (e.compareTo(node.e) > 0){
            node.right = add(node.right,e);
        }

        return node;
    }


    /*
    * 前序遍历 中序遍历 后序遍历
    *
    * 前序遍历
    * 当前节点 左子节点 右子节点
    *
    * 中序遍历
    * 左子节点 当前节点 右子节点
    *
    * 后序遍历
    * 左子节点 右子节点 当前节点
    * */
    public void preOrder(){
        preOrder(root);
    }

    private void preOrder(Node node){
        //终止条件
        //node左或右没有值是 就会为null 下面没有节点就不用遍历了
        if (node == null){
            return;
        }

        System.out.print(node.e+" ");

        preOrder(node.left);
        preOrder(node.right);
    }

    public void midOrder(){
        midOrder(root);
    }

    private void midOrder(Node node){
        //终止条件
        if (node==null){
            return;
        }

        midOrder(node.left);

        System.out.print(node.e+" ");

        midOrder(node.right);
    }

    public void aftOrder(){
        aftOrder(root);
    }

    private void aftOrder(Node node){
        //终止条件
        if (node==null){
            return;
        }

        midOrder(node.left);

        midOrder(node.right);

        System.out.print(node.e+" ");

    }

    public void widthOrder(){
        //层序遍历
    }

}

class a {
    public static void main(String[] args) {
        BinarySearchTree<Integer> ibt = new BinarySearchTree<>();
        ibt.add(8);
        ibt.add(3);
        ibt.add(9);
        ibt.add(2);
        ibt.add(5);
        ibt.add(6);
        ibt.add(12);
        ibt.add(4);
        ibt.preOrder();
        System.out.println();
        ibt.midOrder();
        System.out.println();
        ibt.aftOrder();

    }
}